0450. 删除二叉搜索树中的节点【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 递归

1. 📝 题目描述

• leetcode

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

---

示例 1：

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2：

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3：

输入: root = [], key = 0
输出: []

---

提示：

• 节点数的范围 [0, 10^4].
• -10^5 <= Node.val <= 10^5
• 节点值唯一
• root 是合法的二叉搜索树
• -10^5 <= key <= 10^5

进阶：要求算法时间复杂度为 O(h)，h 为树的高度。

2. 🎯 s.1 - 递归

c

struct TreeNode* deleteNode(struct TreeNode* root, int key) {
    if (!root) return NULL;
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        if (!root->left) { struct TreeNode* r = root->right; free(root); return r; }
        if (!root->right) { struct TreeNode* l = root->left; free(root); return l; }
        struct TreeNode* succ = root->right;
        while (succ->left) succ = succ->left;
        root->val = succ->val;
        root->right = deleteNode(root->right, succ->val);
    }
    return root;
}

js

/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function (root, key) {
  if (!root) return null
  if (key < root.val) {
    root.left = deleteNode(root.left, key)
  } else if (key > root.val) {
    root.right = deleteNode(root.right, key)
  } else {
    if (!root.left) return root.right
    if (!root.right) return root.left
    // 找右子树最小节点
    let successor = root.right
    while (successor.left) successor = successor.left
    root.val = successor.val
    root.right = deleteNode(root.right, successor.val)
  }
  return root
}

py

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            succ = root.right
            while succ.left:
                succ = succ.left
            root.val = succ.val
            root.right = self.deleteNode(root.right, succ.val)
        return root

• 时间复杂度：$O(h)$，其中 $h$ 是树的高度
• 空间复杂度：$O(h)$

算法思路：

• 递归查找目标节点，找到后分三种情况处理
• 若无左子树或无右子树，直接用另一侧替代
• 若左右子树都存在，用右子树最小节点（后继）替代当前节点，再递归删除后继